#include <stdio.h>
#include <stdlib.h>

void swap(int *value1, int *value2)
{
    int temp = 0;
    temp = *value1;
    *value1 = *value2;
    *value2 = temp;
    return;
}
/* quick sort algorithm
 * [input]:
 * @input_arr:  the array needed to be sorted
 * @lo:         (low)the first index of the array
 * @hi:         (high)the last index of the array
 */
void quick_sort(int *input_arr, int lo, int hi)
{
    if (lo >= hi)
    {
        return;
    }

    /* if user want to change the pivot,
     * you can use swap() function first to
     * change the position of the pivot to lo
     */
    int pivot = lo;
    int temp_ref = input_arr[pivot];
    int left_index = lo + 1;
    int right_index = hi;
    while (left_index <= right_index)
    {
        if (left_index == right_index)
        {
            /*
            if (input_arr[pivot] > input_arr[left_index])
            {
                swap(&input_arr[pivot], &input_arr[left_index]);
            }
            else
            {
                left_index--;
            }*/
            if (input_arr[pivot] < input_arr[left_index])
            {
                left_index--;
            }
            swap(&input_arr[pivot], &input_arr[left_index]);
            break;
        }
        if (input_arr[right_index] > temp_ref)
        {
            right_index--;
            continue;
        }
        if (input_arr[left_index] <= temp_ref)
        {
            left_index++;
            continue;
        }
        swap(&input_arr[left_index], &input_arr[right_index]);
    }
    quick_sort(input_arr, lo, left_index - 1);
    quick_sort(input_arr, left_index + 1, hi);
    return;

}
int main(int argc, char *argv[])
{
    int test[] = {109,90,467,3,1,70,78,43,2,1,4,7,88,44,55,190};
    int i = 0;
    int size = sizeof(test) / sizeof(int);
    quick_sort(test, 0, size - 1);
    for (i = 0; i < size; i++)
    {
        printf("%d\n", test[i]);
    }
    return 0;
}

/*
 * NOTES:
 * pivot should not be include in the process.
 * because pivot may be swapped in the process.
 * two points:
 * 1. the pivot's value must appear at the position when sort ends;
 * 2. the pivot's value must be one of the array
 */